package 链表和树.二叉树;
//Java：验证二叉搜索树
public class ValidateBinarySearchTree{
    public static void main(String[] args) {
        Solution solution = new ValidateBinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //二叉树的三种基本遍历方式如下：
    //前序遍历 (Pre-order Traversal)：
    //遍历顺序：根节点 → 左子树 → 右子树
    //也称为"根左右"
    //中序遍历 (In-order Traversal)：
    //遍历顺序：左子树 → 根节点 → 右子树
    //也称为"左根右"
    //对于二叉搜索树(BST)，中序遍历会得到有序序列
    //后序遍历 (Post-order Traversal)：
    //遍历顺序：左子树 → 右子树 → 根节点
    //也称为"左右根"
class Solution {

        //1.验证二叉搜索树 方法一 前序遍历 先判断再递归
    public boolean isValidBST(TreeNode root) {
        //在递归的时候把范围传递过去，根据二叉搜索树的定义遍历左子树时将val作为右边界，遍历右子树时将val作为左边界传递
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }
    private boolean isValidBST(TreeNode node, long left, long right){
        if(node == null){
            return true;
        }
        long number = node.val;

        return left < number && number < right && isValidBST(node.right, number, right)
                && isValidBST(node.left, left, number);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}